package com.链表2;

/**
 * 奇偶链表
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
 *
 * 示例 1:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 1->3->5->2->4->NULL
 */
public class 奇偶链表 {
    static class Solution {
        /**
         * 用双指针完成 odd 奇结点  even 偶节点
         * 给奇结点添加两个哨兵节点才行。
         * 奇偶节点每次移动两个指标。
         *
         * @param head
         * @return
         */
        public ListNode oddEvenList(ListNode head) {
           ListNode odd = new ListNode(-1);
           odd.next = new ListNode(-2);
           odd.next.next = head;
           ListNode even = new ListNode(-1);
           even.next = head;
           ListNode odd2 = odd,even2 = even;
           while (even2 != null && even2.next != null){
               odd2.next = odd2.next.next;
               //移动2的指针也是移动1的指针。否则链表不能连起来。
               odd2 = odd2.next;
               even2.next = even2.next.next;
               even2 = even2.next;
           }
            odd2.next = even.next;
            return odd.next;

        }
    }

    public static void main(String[] args) {
        MyLinkedList link = new MyLinkedList(new int[]{1,2,3});
        Solution solution = new Solution();
        ListNode node = solution.oddEvenList(link.head.next);
//        ListNode pre = new ListNode(-1);
//        pre.next = node;
//        ListNode pre2 = pre;
//        while (pre2 != null && pre2.next != null){
//            pre2.next = pre2.next.next;
//            pre2 = pre2.next;
//        }

    }
}
